#include "SORT.h"

void swap(int* a, int* b)
{
	//printf("%d %d --", *a, *b);
	int tmp = *a;
	*a = *b;
	*b = tmp;
	//printf("%d %d\n", *a, *b);
}

/*******************************************************************************/
/*---------------------------------堆排序------------------------------------- */
/*******************************************************************************/
void heapSort_F(int* arr,int n)//向下调整建堆
{
	//升序建大堆
	int last_father = (n - 1) / 2;					//找到第一个父
	while (last_father != -1)
	{
		int father = last_father;
		int child = father * 2 + 1;
		while (child <= n)
		{
			if (child + 1 <= n && arr[child + 1] > arr[child])		//找到最大的孩子
			{
				++child;
			}
			if (arr[father] < arr[child])					//孩子比父亲大就交换
			{
				int tmp = arr[father];
				arr[father] = arr[child];
				arr[child] = tmp;
			}
			father = child;						//继续向下（大的往上走作为父）
			child = father * 2 + 1;
		}									//大堆好了
		--last_father;
	}
	while (n)
	{
									//交换首尾巴size--
		int tmp = arr[0];
		arr[0] = arr[n];
		arr[n] = tmp;
		--n;

		int father = 0;
		int child = father * 2 + 1;
		while (child <= n)				//向下找大的作为父
		{
			if (child + 1 <= n)
			{
				if (arr[child + 1] > arr[child])++child;
			}
			if (arr[father] < arr[child])
			{
				int tmp = arr[father];
				arr[father] = arr[child];
				arr[child] = tmp;
			}
			father = child;
			child = father * 2 + 1;
		}
	}
}


void heapSort_S(int* arr, int n)//向上调整建堆
{
	//降序建小堆
	for (int i = 1; i <= n; i++)			//从前往后插入，每插入一个判断上面的父是否需要向上改变
	{
		int child = n;
		while (child)
		{
			int father = (child - 1) / 2;
			if (arr[father] > arr[child])
			{
				int tmp = arr[child];
				arr[child] = arr[father];
				arr[father] = tmp;
			}
			child = father;
		}
	}
	while (n)
	{
		int tmp = arr[0];
		arr[0] = arr[n];
		arr[n] = tmp;
		
		--n;
		int father = 0;
		int child = father * 2 + 1;
		while (child <= n)
		{
			if (child + 1 <= n)
			{
				if (arr[child + 1] < arr[child])++child;
			}
			if (arr[father] > arr[child])
			{
				int tmp = arr[father];
				arr[father] = arr[child];
				arr[child] = tmp;
			}
			father = child;
			child = father * 2 + 1;
		}
	}
}
/*=======================================================================================*/
/*=======================================================================================*/


/*******************************************************************************/
/*--------------------------------插入排序------------------------------------ */
/*******************************************************************************/
void InsertSort(int* arr, int n)
{
	int end = 0;
	while (end != n - 1)
	{
		++end;
		int val = arr[end];
		int change = end;
		while (change != 0)
		{
			if (arr[change - 1] > val)
			{
				arr[change] = arr[change - 1];
				--change;
			}
			else break;
		}arr[change] = val;
	}
}
//void InsertSort(int* a, int n)
//{
//	//  [0, n-1]
//	for (int i = 0; i < n - 1; i++)
//	{
//		// [0, n-2]是最后一组
//		// [0,end]有序 end+1位置的值插入[0,end]，保持有序
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//				--end;
//			}
//			else
//			{
//				break;
//			}
//		}
//		a[end + 1] = tmp;
//	}
//}
//
/*=======================================================================================*/
/*=======================================================================================*/


/*******************************************************************************/
/*--------------------------------希儿排序------------------------------------ */
/*******************************************************************************/
void ShellSort(int* arr, int n)
{
	int gap = n;
	while(gap>1)
	{
		gap = gap / 3 + 1;
		//for (size_t j=0; j < gap; j++)
		//{
		//	for (size_t i = j; i < n-gap; i+=gap)   //一组一组
		for (size_t i = 0; i < n - gap; ++i)    //多组并着走
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}arr[end + gap] = tmp;
		}
	//}
	}
}
/*=======================================================================================*/
/*=======================================================================================*/


/*******************************************************************************/
/*------------------------------  选择排序  ---------------------------------- */
/*******************************************************************************/
void SelectSort(int* arr, int n)
{
	int start = 0; int end = n - 1;
	while (start < end)
	{
		int mini = start;
		int maxi = end;
		for (int i = start; i <= end; i++)
		{
			if (arr[i] < arr[mini])mini = i;
			if (arr[i] > arr[maxi])maxi = i;
		}
		//printf("min=%d  max=%d\n ", arr[mini], arr[maxi]);
		if (maxi == start && mini == end)
		{
			swap(&arr[start], &arr[mini]);
		}
			else if (maxi == start || mini == end)
			{
				if (maxi == start)
				{
					swap(&arr[end], &arr[maxi]);
					swap(&arr[start], &arr[mini]);
				}
				if (mini == end)
				{
					swap(&arr[start], &arr[mini]);
					swap(&arr[end], &arr[maxi]);
				}
			}
				else
				{
					swap(&arr[start], &arr[mini]);
					swap(&arr[end], &arr[maxi]);
				}
		++start;
		--end;
	}
}
/*=======================================================================================*/
/*=======================================================================================*/


/*******************************************************************************/
/*--------------------------------快速排序------------------------------------ */
/*******************************************************************************/
int get_midi(int* arr, int left, int right)
{
	int midi = (left + right) / 2;
	if (arr[midi] < arr[left])
	{
		if (arr[midi] > arr[right])return midi;
		else
		{
			if (arr[left] > arr[right])return left;
			else return right;
		}
	}
	else
	{
		if (arr[midi] < arr[right])return midi;
		else
		{
			if (arr[left] > arr[right])return left;
			else return right;
		}
	}
}
// 霍尔版
int partSort1(int* arr, int left, int right)
{
	if (right - left < 10)//小区间优化
	{
		InsertSort(&arr[left], right - left + 1);
	}
	int midi = get_midi(arr, left, right);
	int keyi = left;
	swap(&arr[midi], &arr[keyi]);
	int key = arr[left];
	int begin = left, end = right;
	while (begin < end)
	{
		//向右找小
		while (arr[end] >= key && begin < end)
		{
			--end;
		}
		//向左找大
		while (arr[begin] <= key && begin < end)
		{
			++begin;
		}
		swap(&arr[begin], &arr[end]);
	}
	swap(&arr[keyi], &arr[end]);
	return begin;
}
// 双指针
int partSort2(int* arr, int left, int right)
{
	int keyi = left;
	int key = arr[left];
	int prev = left;
	int cur = prev + 1;
	while (cur<=right)
	{
		if (arr[cur] < key && ++prev != cur)
			swap(&arr[cur], &arr[prev]);
		++cur;
	}
	swap(&arr[prev], &arr[keyi]);
	return prev;
}
//面对顺序的优化：
// 1 随机key   
// 2 三值取中
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)return;
	else
	{
		int begin = partSort2(arr, left, right);
		//int begin = partSort1(arr, left, right);
		QuickSort(arr, left, begin - 1);
		QuickSort(arr, begin + 1, right);
	}
	
}
/*=======================================================================================*/
/*=======================================================================================*/

/*******************************************************************************/
/*---------------------------快速排序（非递归）------------------------------- */
/*******************************************************************************/
void quickSortNonR(int* arr, int left, int right)
{
	ST st;
	STinit(&st);
	STpush(&st, left);
	STpush(&st, right);
	while (!STEmpty(&st))
	{
		int end = STtop(&st);
		STpop(&st);
		int begin = STtop(&st);
		STpop(&st);
		int mid = partSort1(arr, begin, end);
		if (mid - 1 > begin)
		{
			STpush(&st, begin);
			STpush(&st, mid - 1);
		}
		if (mid + 1 < end)
		{
			STpush(&st, mid + 1);
			STpush(&st, end);
		}
	}
}
/*=======================================================================================*/
/*=======================================================================================*/



/*******************************************************************************/
/*--------------------------------归并排序------------------------------------ */
/*******************************************************************************/
void _mergeSort(int* arr, int* tmp, int begin, int end)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;

	_mergeSort(arr, tmp, begin, mid);
	_mergeSort(arr, tmp, mid + 1, end);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;

	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
		tmp[i++] = arr[begin1++];
	while (begin2 <= end2)
		tmp[i++] = arr[begin2++];
	memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void mergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_mergeSort(arr, tmp, 0, n-1);
	free(tmp);
}
/*=======================================================================================*/
/*=======================================================================================*/


/*******************************************************************************/
/*--------------------------------计数排序------------------------------------ */
/*******************************************************************************/

void count_Sort(int* arr,int sz)
{
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < sz; i++)
	{
		if (arr[i] > max)
			max = arr[i];
		if (arr[i] < min)
			min = arr[i];
	}
	int* tmp = (int*)calloc(max - min + 1, sizeof(int));
	for (int i = 0; i < sz; i++)
	{
		tmp[arr[i] - min]++;
	}
	int i = 0;
	for (int j = 0; j < max - min + 1; j++)
	{
		while (tmp[j]--)
		{
			arr[i++] = j + min;
		}
	}
}

/*=======================================================================================*/
/*=======================================================================================*/


/*******************************************************************************/
/*---------------------------归并排序（非递归）------------------------------- */
/*******************************************************************************/
void mergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int j = i;
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (begin2 >= n)
				break;
			if (end2 >= n)
				end2 = n - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
				tmp[j++] = arr[begin1++];
			while (begin2 <= end2)
				tmp[j++] = arr[begin2++];
			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}
/*=======================================================================================*/
/*=======================================================================================*/
